The use of computers and computer software in all of their various forms is recognized to be very common and is growing everyday. In industrialized nations, hardly a business exists that does not rely on computers and software either directly or indirectly, in their daily operations. As well, with the expansion of powerful communication networks such as the Internet, the ease with which computer software programs and data files may be accessed, exchanged, copied and distributed is also growing daily.
In order to take advantage of these computer and communication systems and the efficiencies that they offer, there is a need for methods of storing and exchanging computer software and information securely. Information security issues can generally be categorized as one of the following:    A) confidentiality or privacy, where the goal is to prevent information from being obtained and understood by others;    B) data integrity, where the goal is either to prevent the alteration of data or to advise an authorized party that a set of data has been tampered with;    C) authentication, where the goal is to affirm the identity of a party; or    D) non-repudiation, where the goal is to prevent a party from denying that they made a certain communication. Non-repudiation is often used in electronic commerce transactions, particularly in bidding and negotiation environments.
One method of maintaining confidentiality or privacy that has demonstrated widespread use and acceptance is encryption of data using secret cryptographic keys. Such methods are generally accepted as secure, as an attacker must perform an impractically large number of mathematical tests to identify the cryptographic key required to decode a given encrypted data file. Cracking the Data Encryption Standard (DES) for example, would require an average of 255different keys to be tested, requiring more than 1 thousand years of testing at a rate of one million key tests per second. DES is just one of several block cipher methods which are very fast and are widely used—block ciphers are schemes in which data is divided up into blocks which are encrypted and decrypted separately from one another. If the cryptographic key is kept secure, it offers very good security.
There are many applications, however, in which the encryption key or other secret information (such as biometric data) must be hidden in application software itself. One such example is a Smart Card. Smart Cards are credit card-sized devices which have a small amount of electronic memory and a small microprocessor. They are often used in electronic commerce applications or to record personal information such as health records.
Existing encryption systems are designed to protect their secret keys or other secret data against a “black box attack”. This is a situation where the attacker has knowledge of the algorithm and may examine various inputs to and outputs from the algorithm, but has no visibility into the execution of the algorithm itself. Typical black box attacks are categorized as follows:    A) ciphertext-only attacks, where the attacker attempts to deduce the secret key or plaintext by analysing only the ciphertext;    B) known-plaintext attacks, where the attacker has sets of plaintext and corresponding ciphertext which he can analyse;    C) chosen-plaintext attacks where the attacker can execute the targeted algorithm on plaintext he has chosen, and compare it to the corresponding ciphertext; and    D) adaptive chosen-plaintext attacks, where the attacker modifies the plaintexts he selects for encryption, based on the results of previous analyses.
While such attacks are powerful enough by themselves, it has been shown that the black box model does not reflect reality. Often, if the attacker has sufficient access to the targeted algorithm to mount an adaptive chosen-plaintext attack, he is also in a position to observe at least some aspect of the execution of the algorithm itself.
For example, in their paper on Differential Power Analysis (DPA) titled: Introduction to differential power analysis and related attacks, 1998 (available on the Internet at http://www.cryptography.com/dpa/technical), Paul Kocher, Joshua Jaffe and Benjamin Jun demonstrated that Smart Cards protected with DES could be cracked in a matter of minutes rather than the theoretical thousand years of testing. DPA merely monitors the power consumed by the Smart Card while it is executing the DES algorithm on a chosen input. The power-consumed by the Smart Card at any given point in time corresponds with the bias state of the transistors in the device. The DPA attack can thus deduce the number of bits that are correct in a proposed key by statistical analysis, converging to the correct key very quickly.
The DPA attack shows that having very limited access to the execution of an algorithm designed to defend against a black box attack, is sufficient to make that algorithm completely insecure. Therefore, encryption algorithms must be designed to be secure against a much more powerful attack model—the “white box attack”. A white box attack is simply an attack on a software algorithm in which the attacker has full visibility into the execution of the algorithm (note that the DPA attack may be characterised as a “grey box attack” because the attacker is only able to observe a small part of the execution).
Unfortunately, existing encryption and decryption algorithms and related algorithms including those for digital signatures, password authentication, Smart Cards and the like, are not resistant to white box attacks. In fact, many believe it is impossible to achieve such protection.
Several approaches have been suggested, but offer very weak protection. For example:    A) existing general-purpose commercial software obfuscators use a variety of techniques including: removal of debugging information, changing variable names, introducing irreducible flow graphs, and particularly in the case of Java, modifying code structures to avoid stereotyped forms for source control structures. These methods produce superficial changes, but the information exposed by deeper analyses employed by optimizing compilers and similar sophisticated tools is changed very little. The data flow and control flow information exposed by such analyses is either not affected at all, or is only slightly affected, by the above methods of obfuscation;    B) attempts have also been made to hide the real code by introducing dummy code, for example, by making every other statement a dummy statement designed to look much like the real code. Along with the higher overhead created, this approach has two fatal weaknesses:            i) it is vulnerable to data flow analysis (DFA) to discover the dummy code; and        ii) even if DFA can be rendered ineffective, if x% of the code is dummy code, then 100-x% of the code is significant. For realistic values of x, a patient attacker can locate which statements matter and which do not, by trial and error; and            C) U.S. Pat. No. 5,892,899 titled “Tamper Resistant Methods and Apparatus”, issuing to Aucsmith et al. makes two suggestions:            i) splitting the cryptographic key into pieces stored in different locations in the software code, and        ii) encoding a program in separate sections, decoding only those sections needed, when they are to be executed.        Neither of these approaches is effective as the software code always executes in an unprotected form. Careful tracing of the execution therefore allows the pieces to be reassembled, yielding the complete and unprotected program.        
As well, in their patent application serial no. PCT/US98/12017, Christian Collberg, Clark Thomborsson and Douglas Crow present slightly more sophisticated variations on these themes. While these techniques might sufficiently obscure a key (for example) against a generic, automated attack, they are not resistant to a rigorous white box attack. In most cases, simply tracing execution of the software code will reveal the encryption key and any secure data completely.
Collberg et al, for example, suggest making some simple linear transformations to data values. A careful tracing of the program execution will identify how these transformations are done and undone. As well, since these transformations are linear, they can be reduced.
In addition, a variety of cryptographically weak approaches have been used for encryption and decryption, which avoid the use of any explicit key whatever. These methods are vulnerable either to a cryptographic black-box attack if plain-text can be recognized in an automated way, or to algorithmic analysis with the aid of debugging tools, since the would-be encryption is then a data transformation of quite limited algorithmic complexity.
In general, then, the state of the art has been that programs could not be made effectively secret-hiding and tamper-resistant. In particular, cryptographic keys for reasonably secure ciphers could not be securely hidden in software.
There is therefore a need for a method, apparatus and system for encryption that is tamper-resistant, allowing secret cryptographic keys, biometric data and encrypted data to have software operations executed upon it, without fear that security will be breached.